package leetcode.binaryTree;

import datastructure.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 * 给定两个整数数组preorder 和 inorder，其中preorder 是二叉树的先序遍历， inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 * <p>
 * 草稿(旧) 8
 * @Author Ammar
 * @Create 2023/3/31 21:35
 */
public class _105_从前序与中序遍历序列构造二叉树 {

    static int[] preorder_s;
    static Map<Integer, Integer> inorderMap = new HashMap<>();

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        // 给中序遍历添加索引
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        preorder_s = preorder;
        return buildTree(0, preorder.length - 1, 0, inorder.length - 1);
    }

    /**
     * 递归根据前序遍历特性找到根节点，然后构造根节点的左子树和右子树
     * @param ps
     * @param pe
     * @param is
     * @param ie
     * @return
     */
    public static TreeNode buildTree(int ps, int pe, int is, int ie) {
        if (pe < ps || ie < is) return null;
        int preorderStart;
        int preorderEnd;
        int nodeCount;
        int inorderStart;
        int inorderEnd;

        int root = preorder_s[ps];
        int rootIndex = inorderMap.get(root);
        TreeNode<Integer> rootNode = new TreeNode<>(root, null);

        preorderStart = ps + 1;
        nodeCount = rootIndex - is;
        preorderEnd = ps + nodeCount;
        inorderStart = is;
        inorderEnd = rootIndex - 1;
        rootNode.left = buildTree(preorderStart, preorderEnd, inorderStart, inorderEnd);
        nodeCount = ie - rootIndex;
        preorderStart = pe - nodeCount + 1;
        preorderEnd = pe;
        inorderStart = rootIndex + 1;
        inorderEnd = ie;
        rootNode.right = buildTree(preorderStart, preorderEnd, inorderStart, inorderEnd);
        return rootNode;
    }

    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        buildTree(preorder, inorder);
    }
}
